---
title: "L2-032 彩虹瓶"
created: 2025-11-28
tags:
  - 算法
---

# L2-032 彩虹瓶

## 题目 [L2-032 彩虹瓶](https://pintia.cn/problem-sets/994805046380707840/exam/problems/type/7?problemSetProblemId=1111914599412858889&page=1)

![[image-894bdc4e.png]]

## 思路分析

![[image-10c74dd7.png]]

问题提炼出来

实际是问 给定入栈顺序 能不能以123456……n的顺序出栈 （加一个条件栈深不得超过m）

![[PixPin_2025-04-08_17-54-44-83cc2535.gif]]

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

using ll = long long;

using ull = unsigned long long;

using PII = pair<int ,int>;

using Pll = pair<ll,ll>;

int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

int n,m,k;

bool check(vector<int> pushV,vector<int> popV){

	stack<int> stk;

	int i=0;

	for(auto x:pushV){

		if(x==popV[i]){

			i++;

			while(!stk.empty() && stk.top()==popV[i]){

				stk.pop();

				i++;

			}

		}else{

			stk.push(x);

			if(stk.size()>m){

				return false;

			}

		}

	}

	return stk.empty();

}

int main(){

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	cin>>n>>m>>k;

	vector<int> popV(n);

	for(int i=0;i<n;i++){

		popV[i]=i+1;

	}

	while(k--){

		vector<int> pushV(n);

		for(int i=0;i<n;i++){

			cin>>pushV[i];

		}

		if(check(pushV,popV)){

			cout<<"YES"<<endl;

		}else{

			cout<<"NO"<<endl;

		}

	}

	return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[L2-031 深入虎穴|L2-031 深入虎穴]] 🏠 [[00-天梯赛]] ➡️ [[L2-033 简单计算器|L2-033 简单计算器]]